//
// Created by Incredible on 17/3/16.
//

#ifndef HEAPSORT_HEAP_H
#define HEAPSORT_HEAP_H

#include <iostream>
#include <cassert>
#include <math.h>

using namespace std;

template<typename Item>
class MaxHeap {

private:
    Item *data;
    int count;
    int capacity;


    void shiftUp(int k) {

        //优化点，将交换变成赋值后插入
        Item v = data[k];

        int j = k;  //保存插入节点和是位置的索引

        //while (k > 1 && data[k / 2] < data[k]) {
        while (k > 1 && data[k / 2] < v) {
            //swap(data[k / 2], data[k]);

            data[k] = data[k / 2];
            k /= 2;
            j = k;
        }

        data[j] = v;
    }

    void shiftDown(int k) {

        //优化点：将多次交换变为赋值后插入
        Item v = data[k];

        while (2 * k <= count) {//判断数组有没有越界

            int j = 2 * k;      //在本次循环中，索引k与j的进行交换（默认左孩子）

            if (j < count && data[j + 1] > data[j]) {  //寻找较大的孩子结点，
                j += 1;
            }

//            if (data[k] >= data[j]) {   //父节点与较大的孩子大于相等就不交换
//                break;
//            }

            if (v >= data[j]) {   //待调整元素与将挑换元素大于相等就不赋值
                break;
            }

            //swap(data[k], data[j]);   //替换父子节点位置
            data[k] = data[j];      //将替换元素数值赋值给父节点

            k = j;      //下一个待调整元素的索引位置
        }
        data[k] = v;
    }

    void heapify(int capacity) {
        while (capacity / 2 > 0) {
            shiftDown(capacity / 2);
            capacity--;
        }
    }

public:
    MaxHeap(int capacity) {
        data = new Item[capacity + 1];
        count = 0;
        this->capacity = capacity;
    }

    MaxHeap(Item arr[], int capacity) {
        data = new int[capacity+1];
        this->capacity = capacity;
        for (int i = 0; i < capacity; ++i) {
            data[i+1] = arr[i];
        }
        count = capacity;

        heapify(capacity);
    }

    ~MaxHeap() {
        delete[] data;
    }

    int size() {
        return count;
    }

    bool isEmpty() {
        return count == 0;
    }

    void insert(Item item) {

        assert(count + 1 <= capacity);

        data[count + 1] = item;
        count++;
        shiftUp(count);
    }

    Item extracMax() {

        assert(count > 0);      //堆是否为空

        Item ret = data[1];     //返回最大的值

        swap(data[1], data[count]); //交换最大的结点与最后一个结点；也可以将最后一个元素赋值给第一个元素

        count--;        //堆大小减1

        shiftDown(1);   //维护堆，将data[i]的元素调整到应该的位置

        return ret;
    }
};

#endif //HEAPSORT_HEAP_H
